package com.labuladong.sort;

import java.util.Arrays;

public class MergeSort {

    // 辅助数组，用于合并操作时暂存数据
    private int[] temp;

    // 主函数入口，开始对整个数组进行排序
    public void mergeSort(int[] nums) {
        // 初始化辅助数组
        temp = new int[nums.length];
        // 调用递归排序函数
        sort(nums, 0, nums.length - 1);
    }

    // 递归函数，负责分割数组并分别排序
    private void sort(int[] nums, int lo, int hi) {
        if (lo == hi) {
            // 单个元素不需要排序
            return;
        }
        int mid = lo + (hi - lo) / 2;
        // 对左半部分进行排序
        sort(nums, lo, mid);
        // 对右半部分进行排序
        sort(nums, mid + 1, hi);
        // 合并两部分有序数组
        merge(nums, lo, mid, hi);
    }

    // 合并两个有序数组
    private void merge(int[] nums, int lo, int mid, int hi) {
        // 将原数组对应部分复制到辅助数组中
        for (int i = lo; i <= hi; i++) {
            temp[i] = nums[i];
        }

        // 初始化指针
        int i = lo, j = mid + 1;
        // 遍历目标数组区间，根据比较结果填充正确位置
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                // 左半边已全部放入，从右半边取数
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                // 右半边已全部放入，从左半边取数
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                // 当前左半边元素大于右半边，从右半边取数
                nums[p] = temp[j++];
            } else {
                // 当前左半边元素不大于右半边，从左半边取数
                nums[p] = temp[i++];
            }
        }
    }

    // 测试代码
    public static void main(String[] args) {
        MergeSort sorter = new MergeSort();
        int[] nums = {3, 7, 5, 2, 6, 4, 5, 1};
        System.out.println("Before sorting: " + Arrays.toString(nums));
        sorter.mergeSort(nums);
        System.out.println("After sorting: " + Arrays.toString(nums));
    }
}